//在英语中，我们有一个叫做 词根(root)的概念，它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如，词根an，
//跟随着单词 other(其他)，可以形成新的单词 another(另一个)。 
//
// 现在，给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根，则用最短的词根替换它。 
//
// 你需要输出替换之后的句子。 
//
// 
//
// 示例 1： 
//
// 输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by th
//e battery"
//输出："the cat was rat by the bat"
// 
//
// 示例 2： 
//
// 输入：dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
//输出："a a b c"
// 
//
// 示例 3： 
//
// 输入：dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa a
//aa aaaaaa bbb baba ababa"
//输出："a a a a a a a a bbb baba a"
// 
//
// 示例 4： 
//
// 输入：dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattle
//d by the battery"
//输出："the cat was rat by the bat"
// 
//
// 示例 5： 
//
// 输入：dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is
// accepted"
//输出："it is ab that this solution is ac"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= dictionary.length <= 1000 
// 1 <= dictionary[i].length <= 100 
// dictionary[i] 仅由小写字母组成。 
// 1 <= sentence.length <= 10^6 
// sentence 仅由小写字母和空格组成。 
// sentence 中单词的总量在范围 [1, 1000] 内。 
// sentence 中每个单词的长度在范围 [1, 1000] 内。 
// sentence 中单词之间由一个空格隔开。 
// sentence 没有前导或尾随空格。 
// 
// Related Topics 字典树 数组 哈希表 字符串 
// 👍 137 👎 0
#include <iostream>
#include <string>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
const int N = 500010;
class Solution {
public:
    int ch[N][26],tag[N],tot = 0;
    string replaceWords(vector<string>& dictionary, string sentence) {
        for(int i = 0;i < dictionary.size();i++) insert(dictionary[i]);
        //字符匹配 如果字符的子串出现在trie中，则替换
        vector<string> words = Split(sentence);
        string res;
        for(int i = 0;i < words.size();i++){
            string tmp;
            for(int j = 0;j < words[i].size();j++){
                tmp += words[i][j];
                bool flag = search(tmp);
                if(flag){
                    res += tmp + ' ';
                    break;
                }
                else if(j == words[i].size()-1 && flag == 0 && i != words.size()) res += tmp + ' ';

            }
        }
        res.pop_back();
        return res;
    }
    vector<string> Split(string& str){
        vector<string> res;

        //转化成为stringsteam对象
        stringstream ss(str);

        string curr;

        //使用std::getline方法按照空格分割stringstream对象ss，并把结果存储到curr当中
        while(std::getline(ss, curr, ' ')){
            if(curr.size() > 0){
                res.push_back(curr);
            }
        }
        return res;
    }
    void insert(string word){
        int p = 0;
        for(int i = 0;i < word.size();i++){
            int c = word[i] - 'a';
            if(!ch[p][c]) ch[p][c] = ++tot;
            p = ch[p][c];
        }
        tag[p] = 1;
    }
    bool search(string word){
        int p = 0;
        for(int i = 0;i < word.size();i++){
            int c = word[i] - 'a';
            if(!ch[p][c]) return false;
            p = ch[p][c];
        }
        return tag[p] == 1;
    }

};
//leetcode submit region end(Prohibit modification and deletion)
